{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Linked List Cycle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #linked-list #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #链表 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: hasCycle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #环形链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个链表的头节点 <code>head</code> ，判断链表中是否有环。</p>\n",
    "\n",
    "<p>如果链表中有某个节点，可以通过连续跟踪 <code>next</code> 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 <code>pos</code> 来表示链表尾连接到链表中的位置（索引从 0 开始）。<strong>注意：<code>pos</code> 不作为参数进行传递&nbsp;</strong>。仅仅是为了标识链表的实际情况。</p>\n",
    "\n",
    "<p><em>如果链表中存在环</em>&nbsp;，则返回 <code>true</code> 。 否则，返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/07/circularlinkedlist.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [3,2,0,-4], pos = 1\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>链表中有一个环，其尾部连接到第二个节点。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/07/circularlinkedlist_test2.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2], pos = 0\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>链表中有一个环，其尾部连接到第一个节点。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/07/circularlinkedlist_test3.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1], pos = -1\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>链表中没有环。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表中节点的数目范围是 <code>[0, 10<sup>4</sup>]</code></li>\n",
    "\t<li><code>-10<sup>5</sup> &lt;= Node.val &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>pos</code> 为 <code>-1</code> 或者链表中的一个 <strong>有效索引</strong> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>你能用 <code>O(1)</code>（即，常量）内存解决此问题吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [linked-list-cycle](https://leetcode.cn/problems/linked-list-cycle/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [linked-list-cycle](https://leetcode.cn/problems/linked-list-cycle/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,2,0,-4]\\n1', '[1,2]\\n0', '[1]\\n-1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def hasCycle(self, head: Optional[ListNode]) -> bool:\n",
    "        slow = fast = head\n",
    "        \n",
    "        while fast and fast.next:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next \n",
    "            if slow == fast: return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def hasCycle(self, head: ListNode) -> bool:\n",
    "        dummy = ListNode('loop')\n",
    "        while True:\n",
    "            if not head:\n",
    "                return False\n",
    "            if head.val == 'loop':\n",
    "                return True\n",
    "            temp = head.next\n",
    "            head.next = dummy\n",
    "            head = temp\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def hasCycle(self, head: ListNode) -> bool:\n",
    "        if head == None:\n",
    "            return False\n",
    "        \n",
    "        curr = head\n",
    "        while curr != None:\n",
    "            temp = curr.next\n",
    "            if temp == head:\n",
    "                return True\n",
    "            curr.next = head\n",
    "            curr = temp\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def hasCycle(self, head: ListNode) -> bool:\n",
    "        dummy=ListNode('nll')\n",
    "        if not head:\n",
    "            return False\n",
    "        while head:\n",
    "            p=head\n",
    "            head=head.next\n",
    "            p.next=dummy\n",
    "            if head==dummy:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def hasCycle(self, head: ListNode) -> bool:\n",
    "        dummy = ListNode('dummy')\n",
    "        while head != None:\n",
    "            if(head.next == dummy):\n",
    "                return True\n",
    "            temp = head\n",
    "            head = head.next\n",
    "            temp.next = dummy\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def hasCycle(self, head: ListNode) -> bool:\n",
    "        save_nodes = []\n",
    "        while head:\n",
    "            if head in save_nodes:\n",
    "                return True\n",
    "            save_nodes.append(head)\n",
    "            temp = head.next\n",
    "            head.next = None\n",
    "            head = temp\n",
    "        return False\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "# class Solution:\n",
    "#     def hasCycle(self, head: Optional[ListNode]) -> bool:\n",
    "#         visited = set()\n",
    "#         cur = head\n",
    "#         while cur:\n",
    "#             if cur in visited:\n",
    "#                 return True\n",
    "#             visited.add(cur)\n",
    "#             cur = cur.next\n",
    "#         return False\n",
    "\n",
    "f = open(\"user.out\", \"w\")\n",
    "while True:\n",
    "    try:\n",
    "        param_1 = input()\n",
    "        param_2 = int(input())\n",
    "        f.write('true\\n' if param_2>-1 else 'false\\n')\n",
    "    except:\n",
    "        break\n",
    "exit()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def hasCycle(self, head: ListNode) -> bool:\n",
    "\n",
    "        flag = False\n",
    "        if not head:\n",
    "            return flag\n",
    "\n",
    "        while 1:\n",
    "            if head.next == None:\n",
    "                break\n",
    "            \n",
    "            if head.next.val == \"t\":\n",
    "                flag = True\n",
    "                break \n",
    "            head.val = \"t\"\n",
    "            head = head.next\n",
    "\n",
    "        return flag\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "# class Solution:\n",
    "#     def hasCycle(self, head: Optional[ListNode]) -> bool:\n",
    "#         visited = set()\n",
    "#         while head:\n",
    "#             visited.add(head)\n",
    "#             head = head.next\n",
    "#             if head in visited:\n",
    "#                 return True\n",
    "#         return False\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def hasCycle(self, head: Optional[ListNode]) -> bool:\n",
    "#         if head:\n",
    "#             if head.next:\n",
    "#                 if head.next.next:\n",
    "#                     slow, fast = head.next, head.next.next\n",
    "#                     while fast and fast.next:\n",
    "#                         if slow == fast:\n",
    "#                             return True\n",
    "#                         else:\n",
    "#                             slow = slow.next\n",
    "#                             fast = fast.next.next\n",
    "#         return False\n",
    "\n",
    "with open('user.out', 'w') as f:\n",
    "    lines = __Utils__().read_lines()\n",
    "    for _ in lines:\n",
    "        pos = int(next(lines))\n",
    "        f.write('false\\n' if pos < 0 else 'true\\n')\n",
    "    exit()\n",
    "\n",
    "class Solution:\n",
    "    def hasCycle(self, head: Optional[ListNode]) -> bool:\n",
    "        pass  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "with open('user.out', 'w') as f:\n",
    "    lines = __Utils__().read_lines()\n",
    "    for _ in lines:\n",
    "        pos = int(next(lines))\n",
    "        f.write('false\\n' if pos < 0 else 'true\\n')\n",
    "    exit()\n",
    "\n",
    "class Solution:\n",
    "    def hasCycle(self, head: Optional[ListNode]) -> bool:\n",
    "        pass  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def hasCycle(self, head: Optional[ListNode]) -> bool:\n",
    "        fade = ListNode(0)\n",
    "        status = False\n",
    "        while head :\n",
    "            if head.next ==fade:\n",
    "                status = True\n",
    "                break\n",
    "            nex = head.next\n",
    "            head.next = fade\n",
    "            head = nex\n",
    "        \n",
    "        return status\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def hasCycle(self, head: Optional[ListNode]) -> bool:\n",
    "        if not head:\n",
    "            return False\n",
    "        # 走过的，把next标记为1\n",
    "        queue = [head]\n",
    "        while queue:\n",
    "            cur = queue[0]\n",
    "            if cur.next:\n",
    "                if cur.next == cur:\n",
    "                    return True\n",
    "                if cur.next.next == 1:\n",
    "                    return True\n",
    "                tmp = cur.next\n",
    "                cur.next = 1\n",
    "                queue.append(tmp)\n",
    "            queue = queue[1:]\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def hasCycle(self, head: Optional[ListNode]) -> bool:\n",
    "        node=head\n",
    "        while (node is not None) and (node.next is not None) and (node.next.next is not None):\n",
    "            node.next=node.next.next\n",
    "            node=node.next\n",
    "            if node.next==node:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def hasCycle(self, head: Optional[ListNode]) -> bool:\n",
    "        if not head:\n",
    "            return False\n",
    "        if not head.next:\n",
    "            return False\n",
    "        pre = ListNode(0)\n",
    "        pre.next = head\n",
    "        while(head.next.next):\n",
    "            if head.next.next==head:\n",
    "                return True\n",
    "            tmp = head.next\n",
    "            head.next = tmp.next\n",
    "            tmp.next = pre.next\n",
    "            pre.next = tmp \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def hasCycle(self, head: Optional[ListNode]) -> bool:\n",
    "        trash = ListNode()\n",
    "        last = head\n",
    "        if head:\n",
    "            cur = head.next\n",
    "        else:\n",
    "            return False\n",
    "        while cur:\n",
    "            if cur == trash:\n",
    "                return True\n",
    "            else:\n",
    "                last.next = trash\n",
    "                last = cur\n",
    "                cur = cur.next\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def hasCycle(self, head: Optional[ListNode]) -> bool:\n",
    "        if head == None:\n",
    "            return False\n",
    "        tmp = ListNode(float('-inf'), None)\n",
    "        while head.next:\n",
    "            if head.next == tmp:\n",
    "                return True\n",
    "            curr = head\n",
    "            head = head.next\n",
    "            curr.next = tmp\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def hasCycle(self, head: Optional[ListNode]) -> bool:\n",
    "        while head and head.next and head.next != head:\n",
    "            head.next = head.next.next\n",
    "            head = head.next\n",
    "        if not head or not head.next:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def hasCycle(self, head: Optional[ListNode]) -> bool:\n",
    "        if not head:\n",
    "            return False\n",
    "        stack=head\n",
    "        if  not stack.next:\n",
    "            return False\n",
    "        pre=ListNode(None)\n",
    "        while stack:\n",
    "            if stack.next==head:\n",
    "                return True\n",
    "            temp=stack.next\n",
    "            stack.next=pre\n",
    "            pre=stack\n",
    "            stack=temp\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def hasCycle(self, head: Optional[ListNode]) -> bool:\n",
    "        exists = set()\n",
    "        l = head\n",
    "        while l:\n",
    "            if l in exists:\n",
    "                return True\n",
    "            r = l.next\n",
    "            l.next = None\n",
    "            exists.add(l)\n",
    "            l = r\n",
    "        return False\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def hasCycle(self, head: Optional[ListNode]) -> bool:\n",
    "        seen = list()\n",
    "        # 遍历链表\n",
    "        while head:\n",
    "            if head in seen:\n",
    "                return True\n",
    "            else:\n",
    "                seen.append(head)\n",
    "                head = head.next\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def hasCycle(self, head: Optional[ListNode]) -> bool:\n",
    "        while head:\n",
    "            if head.val == 100001:\n",
    "                return True\n",
    "            else:\n",
    "                head.val = 100001\n",
    "                head = head.next\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def hasCycle(self, head: Optional[ListNode]) -> bool:\n",
    "        if not head or not head.next:\n",
    "            return False\n",
    "        else:\n",
    "            cur=pre=head\n",
    "            while cur and cur.next:\n",
    "                cur=cur.next.next\n",
    "                pre=pre.next\n",
    "                if pre==cur:\n",
    "                    return True\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def hasCycle(self, head: Optional[ListNode]) -> bool:\n",
    "        if not head or not head.next:\n",
    "            return False\n",
    "        left = head\n",
    "        right = head.next\n",
    "        while left != right:\n",
    "            if not right or not right.next:\n",
    "                return False\n",
    "            left = left.next\n",
    "            right = right.next.next\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def hasCycle(self, head: Optional[ListNode]) -> bool:\n",
    "        fast = head\n",
    "        slow = head\n",
    "        while fast != None and fast.next != None:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            if fast == slow:\n",
    "                return True\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def hasCycle(self, head: Optional[ListNode]) -> bool:\n",
    "        fast, slow = head, head\n",
    "        while fast != None and fast.next != None:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "            if fast == slow:\n",
    "                return True\n",
    "        return False"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
